{
 "cells": [
          {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table align=\"left\">\n",
    "  <td>\n",
    "    <a target=\"_blank\" href=\"https://colab.research.google.com/github/gimseng/99-ML-Learning-Projects/blob/master/010/exercise/knn_starter_exercise.ipynb\"><img src=\"https://www.tensorflow.org/images/colab_logo_32px.png\" />Run in Google Colab</a>\n",
    "  </td>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Importing libraries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# importing necessary libraries\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "import math\n",
    "from collections import Counter\n",
    "from copy import deepcopy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Loading sample data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Sample data with (xp,yp) as positive-class coordinates and (xn,yn) as negative-class coordinates\n",
    "#xp = [-1,0,4,6,7]\n",
    "#yp = [-2,0,4,2,9]\n",
    "#xn = [-3,1,2,4,6,4]\n",
    "#yn = [-2,5,4,2,4,6]\n",
    "\n",
    "xp=[]\n",
    "yp=[]\n",
    "xn=[]\n",
    "yn=[]\n",
    "\n",
    "data = [\n",
    "    (-1,-2,'Positive'),\n",
    "    (7,9,'Positive'),\n",
    "    (0,0,'Positive'),\n",
    "    (4,4,'Positive'),\n",
    "    (6,2,'Positive'),\n",
    "    (-3,-2,'Negative'),\n",
    "    (1,5,'Negative'),\n",
    "    (2,4,'Negative'),\n",
    "    (4,2,'Negative'),\n",
    "    (6,4,'Negative'),\n",
    "    (4,6,'Negative'),\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-1, 7, 0, 4, 6] [-2, 9, 0, 4, 2] [-3, 1, 2, 4, 6, 4] [-2, 5, 4, 2, 4, 6]\n"
     ]
    }
   ],
   "source": [
    "# Append data points in respective arrays for data plotting\n",
    "for i in range(0,len(data)):\n",
    "    if(data[i][2]=='Positive'):\n",
    "        xp.append(data[i][0])\n",
    "        yp.append(data[i][1])\n",
    "    else: \n",
    "        xn.append(data[i][0])\n",
    "        yn.append(data[i][1])\n",
    "        \n",
    "print(xp,yp,xn,yn)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Plotting graph for visualization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXgAAAEGCAYAAABvtY4XAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAUpklEQVR4nO3df5Dcd33f8eeb8xHOvyQaO8I+qzVtmZsksvGhq1OiqeewSGQmDlEzGQ+uoW0mLf0D/4A6SlHS4jHTNJpqwEmmmU492AmdgD2qkdXAUJSMdRtKWoglS+hshApxoNbJ2HiIZMu5wkl5949dSSdzd9JJ+/nu3Wefj5md2/3eel+fr1d+af35fvf7icxEklSf1/V6AJKkMix4SaqUBS9JlbLgJalSFrwkVeqiXg9gtiuuuCKvvfbaXg9DZ/Hqq69yySWX9FV2v+X2Mtt9Xpw9e/a8lJlXzvnLzFwyt7Vr16aWvomJib7L7rfcXma7z4sD7M55OtUpGkmqlAUvSZWy4CWpUha8JFXKgpekShUt+Ii4JyKejohnIuKDJbMkabnZsXeKdVt2MTl1lHVbdrFj71RXX79YwUfEGuBfAjcCbwVujYi3lMqTpOVkx94pNm+fZOrINABTR6bZvH2yqyVf8hP8jwNfzsy/zszjwJ8C/7hgniQtG1t3HmR65sQZ26ZnTrB158GuZUQWuh58RPw48N+BtwPTwBO0T8i/6zXPez/wfoBVq1atffTRR4uMR91z7NgxLr300r7K7rfcXmb3yz5PTh09dX/VELwwffp31w2vOOfXecc73rEnM8fm+l2xggeIiF8BPgAcA74GTGfmh+Z7/tjYWO7evbvYeNQdrVaL8fHxvsrut9xeZvfLPq/bsuvU9My91x3nY5PtK8cMrxzizz588zm/TkTMW/BFD7Jm5kOZ+bbMvAn4HvCNknmStFxs2jDC0ODAGduGBgfYtGGkaxlFLzYWET+WmS9GxN8GfpH2dI0k9b2No8MAnTn3VxheOcSmDSOntndD6atJfiYifhSYAT6QmX9VOE+Slo2No8NsHB2m1Wpx1x3jXX/9ogWfmf+o5OtLkubnN1klqVIWvCRVyoKXpEpZ8JJUKQtekiplwUtSpSx4SaqUBS9JlbLgJalSpVd0+lBnNaenI+KRiHhDyTxJ0mklV3QaBu4GxjJzDTAAvKdUniTpTKWnaC4ChiLiIuBi4HDhPElSR+kFP+4BfpP2ik5/nJl3zPEcV3RaZvplxZ1+zu1ltvu8OAut6ERmFrkBbwR2AVcCg8AO4L0L/TNr165NLX0TExN9l91vub3Mdp8Xh/ZSqHN2askpmncCf5mZ383MGWA78NMF8yRJs5Qs+P8L/MOIuDgiAlgPHCiYJ0mapVjBZ+ZXgMeAp4DJTtaDpfIkSWcqvaLTfcB9JTMkSXPzm6ySVCkLXpIqZcFLUqUseEmqlAUvSZWy4CWpUha8JFXKgpekSlnwklSpkgt+jETEvlm3lyPig6XyJElnKnapgsw8CNwAEBEDwBTweKk8SdKZmpqiWQ/8RWZ+u6E8Sep7RVd0OhUS8TDwVGb+pzl+54pOy4wr7tSf28ts93lxerKi08kb8HrgJWDV2Z7rik7Lgyvu1J/by2z3eXHo0YpOJ72L9qf3FxrIkiR1NFHwtwOPNJAjSZqlaMFHxMXAz9Bej1WS1KDSKzr9NfCjJTMkSXPzm6ySVCkLXpIqZcFLUqUseEmqlAUvSZWy4CWpUha8JFXKgpekSlnwklSp0pcqWBkRj0XE1yPiQES8vWSepC7Yvw0eWAPP72v/3L+t1yPSeSp6qQLgd4AvZOYvRcTrgYsL50m6EPu3wWfvhplpeBNw9Ln2Y4Drb+vp0LR4JddkvRy4CXgIIDN/kJlHSuVJ6oInPtou99lmptvbtewUW9EpIm4AHgS+BrwV2APck5mvvuZ5rui0zLjiTsW5z+87nf0jV3Pp9w+f/t1VNzQyBP98Lc5CKzqVLPgx4MvAusz8SkT8DvByZv67+f6ZsbGx3L17d5HxqHtarRbj4+N9ld03uQ+saU/LAK2R+xk/eF97+4rV8KGnGxmCf74WJyLmLfiSB1kPAYcy8yudx48BbyuYJ+lCrf8IDA6duW1wqL1dy06xgs/M7wDPRcRIZ9N62tM1kpaq62+Dn//d9id2aP/8+d/1AOsyVfosmruAT3XOoHkW+OXCeZIu1PW3tW+tFtzezLSMyii9otM+YM65IUlSWX6TVZIqZcFLUqUseEmqlAUvSZWy4CWpUha8JFXKgpekSlnwklQpC16SKlV6RadvRcRkROyLCC8TqfPnKkPSopW+Fg3AOzLzpQZyVCtXGZLOi1M0WvpcZUg6L8UW/ACIiL8E/gpI4L9k5oNzPMcVnZYZVxlqjqsb9Ud2qRWdyMxiN+Dqzs8fA74K3LTQ89euXZta+iYmJpoN/PhPZt53eeZ9l+fEpx84dT8//pONDaHxfe5xbi+z3efFAXbnPJ1adIomMw93fr4IPA7cWDJPlXKVIem8FCv4iLgkIi47eR/4WcDVA7R4rjIknZeSZ9GsAh6PiJM5n87MLxTMU81cZUhatGIFn5nPAm8t9fqSpIV5mqQkVcqCl6RKWfCSVCkLXpIqZcFLUqUseEmqlAUvSZWy4CWpUha8JFWqeMFHxEBE7I2Iz5XOkrquD1eS2rF3inVbdjE5dZR1W3axY+9Ur4dUXqXvcxMrOt0DHAAubyBL6p4+XElqx94pNm+fZHrmBKyGqSPTbN4+CcDG0eEej66Qit/n0muyXgP8HPCJkjlSEX24ktTWnQfb5T7L9MwJtu482KMRNaDi97n0ik6PAb8FXAb8ambeOsdzXNFpmembFXf6cCWpyamjp+6vGoIXZvXedcMrGhmDK4YtzkIrOhWboomIW4EXM3NPRIzP97xsL+P3IMDY2FiOj8/7VC0RrVaLXr1PjWY/cGf7f9eB1sj9jB+8r719xerGLlnc9L/r39iyi6kj7Va/97rjfGyyXRHDK4e4645mxtH4n6+K3+eSUzTrgHdHxLeAR4GbI+IPC+ZJ3dWHK0lt2jDC0ODAGduGBgfYtGGkRyNqQMXvc8nrwW8GNgN0PsH/ama+t1Se1HUnD7CdnItdsbr9H/0yP/C2kJMHUttz7q8wvHKITRtG6j3AClW/z02cRSMtX324ktTG0WE2jg7TarUam5bpuUrf50YKPjNbQKuJLElSm99klaRKWfCSVKmzFnxE3BkRb2xiMJKk7jmXT/BvAp6MiG0RcUtEROlBSZIu3FkLPjP/LfAW4CHgnwPfiIj/EBF/r/DYJEkX4Jzm4LN9PYPvdG7HgTcCj0XEfyw4NknSBTjraZIRcTfwz4CXaF80bFNmzkTE64BvAL9WdoiSpPNxLufBXwH8YmZ+e/bGzPybzvVmJElL0FkLPjPnvSBDZh7o7nAkSd1S7Dz4iHhDRPx5RHw1Ip6JiPtLZUmSfljJSxV8H7g5M49FxCDwpYj4H5n55YKZkqSOkleTTOBY5+Fg51ZudRFJ0hlKr+g0AOwB/j7we5n5b+Z4jis6LTN9s6JTH+f2Mtt9XpyFVnQiM4vfgJXABLBmoeetXbs2tfRNTEz0XXa/5fYy231eHGB3ztOpjVxsLDOP0L5c8C1N5EmSyp5Fc2VErOzcHwLeCXy9VJ4k6Uwlz6K5CvhkZx7+dcC2zPxcwTxJ0iwlz6LZD4yWen1J0sJc8EOSKmXBS1KlLHhJqpQFL0mVsuAlqVIWvCRVyoKXpEpZ8JJUKQtekipV8lo0qyNiIiIOdFZ0uqdUlqQu2r8NHlgDz+9r/9y/rdcjKm7H3inWbdnF5NRR1m3ZxY69U70eUleUvBbNceDezHwqIi4D9kTEn2Tm1wpmSroQ+7fBZ++GmWl4E3D0ufZjgOtv6+nQStmxd4rN2yeZnjkBq2HqyDSbt08CsHF0uMejuzDFPsFn5vOZ+VTn/ivAAWB5/9uSavfER9vlPtvMdHt7pbbuPNgu91mmZ06wdefBHo2oe4qu6HQqJOJa4Iu0F/x4+TW/c0WnZcYVdyrOfX7f6ewfuZpLv3/49O+uuqGRITS9z5NTR0/dXzUEL8z6++264RWNjKHUik7FCz4iLgX+FPjNzNy+0HPHxsZy9+7dRcejC9dqtRgfH++r7L7JfWBNe1oGaI3cz/jB+9rbV6yGDz3dyBCa3ud1W3YxdaTd6vded5yPTbZnrodXDvFnH765kTFcyD5HxLwFX/QsmogYBD4DfOps5S5pCVj/ERgcOnPb4FB7e6U2bRhhaHDgjG1DgwNs2jDSoxF1T7GDrBERwEPAgcz8eKkcSV108kDqyTn3Favb5V7pAVY4fSC1Pef+CsMrh9i0YWTZH2CFsmfRrAPeB0xGxMmJvV/PzM8XzJR0oa6/rX1rteD2ZqZlem3j6DAbR4dptVrcdcd4r4fTNSVXdPoSEKVeX5K0ML/JKkmVsuAlqVIWvCRVyoKXpEpZ8JJUKQtekiplwUtSpSx4SaqUBS9JlSq5otPDEfFiRPTHd50laYkp+Qn+D4BbCr6+JGkBJVd0+iLwvVKvL0laWNEFPzorOX0uM9cs8BxXdFpmXNGp/txeZrvPi7PQik5kZrEbcC3w9Lk+f+3atamlb2Jiou+y+y23l9nu8+IAu3OeTvUsGkmqlAUvSZUqeZrkI8D/BkYi4lBE/EqpLEnSDyu5otPtpV5bknR2TtFIUqUseEmqlAUvSZWy4CWpUha8JFXKgpekSlnwklQpC16SKmXBS1KlihZ8RNwSEQcj4psR8eGSWSpvx94p1m3ZxeTUUdZt2cWOvVO9HpKkBZS8Fs0A8HvAu4CfAG6PiJ8olaeyduydYvP2SaaOTAMwdWSazdsnLXlpCSv5Cf5G4JuZ+Wxm/gB4FPiFgnkqaOvOg0zPnDhj2/TMCbbuPNijEUk6m2IrOkXELwG3ZOa/6Dx+H/BTmXnna57nik7LwOTU0VP3Vw3BC9Onf3fd8IrGxrEcV9xZjrm9zHafF2ehFZ2KXU0SiDm2/dDfJpn5IPAgwNjYWI6Pjxccks7Xb2zZdWp65t7rjvOxyfYfneGVQ9x1x3hj42i1WvTiz0i/5fYy233unpJTNIeA1bMeXwMcLpingjZtGGFocOCMbUODA2zaMNKjEUk6m5Kf4J8E3hIRbwamgPcA/6RgngraODoM0Jlzf4XhlUNs2jByarukpafkgh/HI+JOYCcwADycmc+UylN5G0eH2Tg6TKvVanRaRtL5KfkJnsz8PPD5khmSpLn5TVZJqpQFL0mVsuAlqVIWvCRVyoKXpEpZ8JJUKQtekiplwUtSpSx4SaqUBS9JlbLgJalSFrwkVcqCl6RKWfCSVCkLXpIqZcFLUqUseEmqlAUvSZWy4CWpUha8JFXKgpekSlnwklQpC16SKmXBS1KlLHhJqpQFL0mVsuAlqVIX9XoAF2z/Nnjio3D0EKy4BtZ/BK6/rdejKmrH3im27jzI4SPTXL1yiE0bRtg4OtzrYUlaYpZ3we/fBp+9G2am24+PPtd+DNWW/I69U2zePsn0zAkApo5Ms3n7JIAlL+kMy3uK5omPni73k2am29srtXXnwVPlftL0zAm27jzYoxFJWqqWd8EfPbS47RU4fGR6Udsl9a/lXfArrlnc9gpcvXJoUdsl9a/lXfDrPwKDrym2waH29kpt2jDC0ODAGduGBgfYtGGkRyOStFQt74OsJw+k9tFZNCcPpHoWjaSzWd4FD+0yr7jQ57JxdNhCl3RWy3uKRpI0LwtekiplwUtSpSx4SaqUBS9JlYrM7PUYTomI7wLf7vU4dFZXAC/1WXa/5fYy231enL+TmVfO9YslVfBaHiJid2aO9VN2v+X2Mtt97h6naCSpUha8JFXKgtf5eLAPs/stt5fZ7nOXOAcvSZXyE7wkVcqCl6RKWfBalIi4JSIORsQ3I+LDDWU+HBEvRsTTTeS9Jnt1RExExIGIeCYi7mko9w0R8ecR8dVO7v1N5M7KH4iIvRHxuYZzvxURkxGxLyJ2N5i7MiIei4ivd97rtzeUO9LZ15O3lyPig117fefgda4iYgD4P8DPAIeAJ4HbM/NrhXNvAo4B/zUz15TMmiP7KuCqzHwqIi4D9gAbG9jnAC7JzGMRMQh8CbgnM79cMndW/r8GxoDLM/PWJjI7ud8CxjKz0S8bRcQngf+ZmZ+IiNcDF2fmkYbHMABMAT+VmV35wqef4LUYNwLfzMxnM/MHwKPAL5QOzcwvAt8rnTNP9vOZ+VTn/ivAAaD4xfiz7Vjn4WDn1sinsYi4Bvg54BNN5PVaRFwO3AQ8BJCZP2i63DvWA3/RrXIHC16LMww8N+vxIRoou6UiIq4FRoGvNJQ3EBH7gBeBP8nMRnKB3wZ+DfibhvJmS+CPI2JPRLy/ocy/C3wX+P3OtNQnIuKShrJnew/wSDdf0ILXYsQc2/piji8iLgU+A3wwM19uIjMzT2TmDcA1wI0RUXx6KiJuBV7MzD2ls+axLjPfBrwL+EBneq60i4C3Af85M0eBV4FGji+d1JkWejfw37r5uha8FuMQsHrW42uAwz0aS2M6c+CfAT6Vmdubzu9MF7SAWxqIWwe8uzMX/ihwc0T8YQO5AGTm4c7PF4HHaU8LlnYIODTr/5Aeo134TXoX8FRmvtDNF7XgtRhPAm+JiDd3PnG8B/ijHo+pqM7BzoeAA5n58QZzr4yIlZ37Q8A7ga+Xzs3MzZl5TWZeS/v93ZWZ7y2dCxARl3QOZNOZIvlZoPiZU5n5HeC5iBjpbFoPFD2IPofb6fL0DNSw6LYak5nHI+JOYCcwADycmc+Uzo2IR4Bx4IqIOATcl5kPlc7tWAe8D5jszIcD/Hpmfr5w7lXAJztnVrwO2JaZjZ6y2AOrgMfbf6dyEfDpzPxCQ9l3AZ/qfHB5FvjlhnKJiItpn5n2r7r+2p4mKUl1copGkiplwUtSpSx4SaqUBS9JlbLgJalSFrwkVcqCl6RKWfDSPCLiH0TE/s612S/pXJe90csVSxfCLzpJC4iIfw+8ARiifb2S3+rxkKRzZsFLC+h8df1J4P8BP52ZJ3o8JOmcOUUjLexvAZcCl9H+JC8tG36ClxYQEX9E+7K5b6a9dN+dPR6SdM68mqQ0j4j4p8DxzPx056qO/ysibs7MXb0em3Qu/AQvSZVyDl6SKmXBS1KlLHhJqpQFL0mVsuAlqVIWvCRVyoKXpEr9fwoK1wccKUTVAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Plot coordinates\n",
    "fig = plt.figure()\n",
    "ax = fig.gca()\n",
    "ax.set_xticks(np.arange(0, 10, 1))\n",
    "ax.set_yticks(np.arange(0, 10, 1))\n",
    "plt.xlabel('x')\n",
    "plt.ylabel('y')\n",
    "\n",
    "plt.scatter(xp,yp)\n",
    "plt.scatter(xn,yn)\n",
    "plt.grid(True)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Writing helper functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def e_distance(x,y):\n",
    "    '''\n",
    "    Method that calculates Euclidean distance from the point to be classified \n",
    "    \n",
    "    to every other point\n",
    "    '''\n",
    "    # write your logic here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def max_Count(vector):\n",
    "    '''\n",
    "    Method for calculating mode of data\n",
    "    '''\n",
    "    # write your logic here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Take test input for classification"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter pts x,y and k: 1 2 3\n"
     ]
    }
   ],
   "source": [
    "# Provide test input for classification in the format 1 2 3 by giving space in between\n",
    "(x1,y1,k) = map(int,input(\"Enter pts x,y and k: \").split(\" \"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Code the KNN algorithm here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def KNN(x1,y1,k):\n",
    "    '''\n",
    "    Method that classifies the test point\n",
    "    \n",
    "    sorts the list and finds mode of the first k tuples to classify point x1,y1\n",
    "    \n",
    "    Call the necessary helper functions\n",
    "    '''    \n",
    "    # write your logic here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# call the function with test points as parameters and value k\n",
    "KNN(x1,y1,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
